主题是推理与动态规划
由于是动态更新的,所以标号可能是乱的,不用在意标号问题,标号只是确定说之前更新到哪了
如果超过个题,就会专门再有一个传送门指向其他的文章.
①[POJ 1082] Calendar Game
原题链接:http://poj.org/problem?id=1082
题面就不放了,这题没啥意思,结论是月和天之和为偶数时先手必胜。但是很弱智的是有特例:和也是先手必胜。
②[POJ 2068] Nim
原题链接:http://poj.org/problem?id=2068
题目大意:有两个队伍,每个队伍有个人,你的队伍先手,即第一个人是你的队伍的人,且标号为,并且两个队伍的人是交替坐成一个圈的。场上一共有个石头,每个人每次取的石头的数量最大值是,且不能不取。问你的队伍是否必胜。
数据范围:
多组测试数据
样例输入:
1 101 4 4
1 100 4 4
3 97 8 7 6 5 4 3
0
0
1
1
这题看起来没什么性质可推,但是数据量由于人数非常小,可以考虑从原始定义出发:即从一个状态如果走到了一个必败态,则前者是必胜态;若走不到任何一个必败态则必败。用求解状态即可,整个局面是一个环,定义状态为当前是第个人,面对的局面是个石子在场上,若必胜为,否则为。状态的转移也比较好想,但是由于说涉及到环和取模,所以这里就使用记忆化以及求出去的状态的方式来做比较简单。具体来说当前的状态取决于当前取了个石块对应的后面一个状态里有没有一个必败态,如果有的话就为,如果遍历了所有的都没有,就是。同时因为是一个环,所以为了方便代码的实现就把位置换成了从开始而非从开始、
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 22,M = 1 << 14;
int f[N][M];
int a[N],n,S;
bool dp(int i,int j)
{
if(!j) return 1;
if(f[i][j] != -1) return f[i][j];
for(int k = 1;k <= a[i];++k)
{
if(j - k < 0) break;
if(dp((i + 1) % (2 * n),j - k) == 0) return f[i][j] = 1;
}
return f[i][j] = 0;
}
int main()
{
while(scanf("%d",&n),n)
{
memset(f,-1,sizeof f);
scanf("%d",&S);
for(int i = 0;i < 2 * n;++i) scanf("%d",&a[i]);
if(dp(0,S)) puts("1");
else puts("0");
}
return 0;
}
③[POJ 3668] Cheat in the game
原题链接:http://poj.org/problem?id=3688
题目大意:Alice和Bob在玩一个取石子游戏,一共有个卡片和最多个石头,每次两个人都会在张卡片中随机的选出一个,卡片上标记的数字就是本回合要取的石子数量,如果不够取就再抽一张,如果卡片抽完了胜者还没判别出来,则游戏重置再来,直到决出胜者为止。问在最多个石头的前提下,有多少种情况可以先手必胜。输出方案数即可。
数据范围:
多组测试数据
样例输入:
3 8
1 5 7
0 0
样例输出:
3
这个题的题意写得不够完整,注意卡片在抽出来了之后是不会反回去的,样例的合法数只有三个:,并且先手必胜的判据是A的胜率是大于,且B的胜率是。虽然游戏可能进行很多次平局导致游戏重开,但是保证B的胜率是0就行了。
最简单也最直接的想法就是枚举所有石头的可能性,于是顺理成章的就想到了尝试一下看能不能把复杂度降下来。思考之后会发现也没法避免枚举,而且方法也不是很明确,说明题目还可能还有什么隐藏的判据没有找出来:
这个题目的选取的个数虽然表面上看是随机的,不过实际上,由于要保证B的胜率一定是,所以说还是得考虑有可能的状态:即保证所有的情况下B都是必输的。因此,可以把“选择”这个条件去掉,变成“组合”,这个题最本质的性质就是:在所有情况中,一个数如果只能被奇数个数表示出来,那么他是必胜的,如果只能被偶数个数表示出来,那么他是必败的。其余的情况结局无法判明,但是至少不是必胜的。
因此就比较好想了:
第一步先要排序,使状态的更新是正确的。
状态:表示这个数,在时为能被偶数个数表示出来,时表示能被奇数个数表示出来。
入口:对于每个来说都有
出口:先手必胜的状态数就是满足f[i][0] == 1 && f[i][1] == 0的数,其中
转移:
若,则有两种:
当时,
当时,
最后统计答案就可以了。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e4+7,M = 1e5+7;
int a[N],f[M][2];
int n,m;
void dp()
{
sort(a + 1,a + 1 + n);
f[a[1]][0] = 1;
for(int i = 2;i <= n;++i)
{
for(int j = m;j > a[i];--j)
{
if(f[j - a[i]][0]) f[j][1] = 1;
if(f[j - a[i]][1]) f[j][0] = 1;
}
f[a[i]][0] = 1;
}
}
int main()
{
while(scanf("%d%d",&n,&m),n || m)
{
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
memset(f,0,sizeof f);
dp();
int res = 0;
for(int i = 1;i <= m;++i)
if(f[i][0] && !f[i][1])
++res;
printf("%d\n",res);
}
return 0;
}
④[POJ 1740]A New Stone Game
原题链接:http://poj.org/problem?id=1740
这题原题面写的很垃圾。
题目大意:Alice和Bob在玩一个新的石子游戏,一共有个石碓,每堆石子里不会超过有个石子。每次操作时,选择一个石碓,丢掉里面的一个石子,下一步可以不操作,也可以选出若干个石子放到另外一个当前非空的任意多个石碓里。最后一个拿走剩下所有石碓的人获胜。A先手,问是否先手必胜。
数据范围:
多组测试数据
样例输入:
3
2 1 3
2
1 1
0
样例输出:
1
0
这题是个规律题,一共也才个,可以枚举一下找结论:
当时,先手必胜
当时,如果两堆石子完全相同,则对手可以镜像操作,导致先手必败。除此之外先手必胜。
当时,先手把一堆石子全部拿空,可以变成且相同的两堆的状态(是人为的构造两个不相同),因为可以任意分配到还有石子的堆里,所以是一定可以到达的。这样就构造了一个先手必败局面给对手,因此必胜。
当时,同可以拓展出一个结论:当为偶数的时候,如果石子可以两两分成两堆相同的组,就是先手必败的。同样,当是奇数是,可以构造出上一个偶数的状态,因此奇数是必胜的。
最后排个序验证一下结论就可以了。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 20;
int n,a[N];
int main()
{
while(scanf("%d",&n),n)
{
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
sort(a + 1,a + 1 + n);
if(n % 2) printf("1\n");
else
{
int ok = 1;
for(int i = 1;i + 1 <= n;i += 2)
{
if(a[i] != a[i + 1])
{
ok = 0;
break;
}
}
if(ok) puts("0");
else puts("1");
}
}
return 0;
}